#include "LinkList.h"
#include <iostream>

LInkList::LInkList():size(0)
{
    head = new Node(0);//头结点
}

LInkList::LInkList(const LInkList &list) //O(n)
{
    size = 0;
    head = new Node(0);
    Node * travelPoint = list.head->next;
    while(travelPoint != nullptr)
    {
        InsertTail(travelPoint->value);
        travelPoint = travelPoint->next;
    }

}

LInkList::~LInkList()
{
    while(head != nullptr)
    {
        Node *nextNode = head->next;//记录下一个结点指针
        delete head;//放掉当前指针
        head = nextNode;//head指针往后走
    }
}
// 尾插
void LInkList::InsertTail(const ElementType &element)  //时间复杂度O(n)
{
    Node * travelPoint = head;  //遍历指针
    //找尾巴
    while (travelPoint->next != nullptr)
    {
        travelPoint = travelPoint->next;
    }
    travelPoint->next = new Node(element);//在尾部插入新的节点
    size++;
}
//头插
void LInkList::InsertHead(const ElementType &element)  //O(1)
{
    Node * newNode = new Node(element);
    newNode->next = head->next;
    head->next = newNode;
    size++;
}
//中间插入
void LInkList::InsertByIndex(int index,const ElementType &element)//O(n):找的过程
{
    if(index < 0 || index > size)//合法值判断
        return;
    Node * travelPoint = head;
    for(int i = 0; i < index; i++)//实际有效值 index - 1位置
    {
        travelPoint = travelPoint->next;
    }
    Node * newNode = new Node(element);
    newNode->next = travelPoint->next;
    travelPoint->next = newNode;
    size++;

}

//按值删除
void LInkList::RemoveByElement(const ElementType &element)
{
    Node * travelPoint = head;
    while(travelPoint->next != nullptr)
    {
        if(travelPoint->next->value == element)
        {
            Node *freeNode = travelPoint->next;
            travelPoint->next = freeNode->next;
            delete freeNode;
            size--;
        }
        else
            travelPoint = travelPoint->next;
    }
}

//按位置删除
void LInkList::RemoveByIndex(int index) //O(n)
{
    if(index < 0 || index >= size)//合法值判断
        return;
    Node * travelPoint = head;
    for(int i = 0; i < index; i++) //实际有效值 index - 1位置
    {
        travelPoint = travelPoint->next;
    }
    Node *freeNode = travelPoint->next;
    travelPoint->next = freeNode->next;
    delete freeNode;
    size--;
}

void LInkList::UpdataByIndex(int index, const ElementType &element)
{
    if(index < 0 || index >= size)//合法值判断
        return;
    Node * travelPoint = head;
    for(int i = 0; i <= index; i++)
    {
        travelPoint = travelPoint->next;
    }
    travelPoint->value = element;
    
}

void LInkList::UpdataByElement(const ElementType &oldValue, const ElementType &newValue)
{
    Node * travelPoint = head->next;
    while(travelPoint != nullptr)
    {
        if(travelPoint->value == oldValue)
        {
            travelPoint->value = newValue;
        }
        travelPoint = travelPoint->next;
    }
}

//冒泡排序
void LInkList::BubbleSore() //O(n^2)
{
    for(int i = 0; i < size -1; i++)
    {
        Node * travelPoint = head;//从头开始扫描链表
        for(int j = 0; j < size -i - 1;j++)
        {
            if(travelPoint->next->value > travelPoint->next->next->value)
            {
                Node *prevNode = travelPoint->next;
                Node *nextNode = prevNode->next;

                travelPoint->next = nextNode;
                prevNode->next = nextNode->next;
                nextNode->next = prevNode;
            }
 
            travelPoint = travelPoint->next;

        } 
    }
}

//归并
LInkList LInkList::Merge(const LInkList &list)
{
    LInkList result;
    Node *p1 = head->next;
    Node *p2 = list.head->next;
    while(p1 && p2)
    {
        if(p1->value < p2->value)
        {
            result.InsertTail(p1->value);
            p1 = p1->next;
        }
        else
        {
            result.InsertTail(p2->value);
            p2 = p2->next;
        }
    }
    while(p1)
    {
        result.InsertTail(p1->value);
        p1 = p1->next;
    }
    while(p2)
    {
        result.InsertTail(p2->value);
        p2 = p2->next;
    }

    return result;
}

void LInkList::Sort()
{
    FastSort(head->next,nullptr);
}


//链表逆序
void LInkList::Reserve()
{
    Node *prev = nullptr;
    Node *cur = head->next;
    Node *Next = cur->next;
    while(Next != nullptr)
    {
        cur->next = prev;//逆序
        prev = cur;
        cur = Next;
        Next = cur->next;

    }
    cur->next = prev; //最后的一个结点单独逆序
    head->next = cur; 
}


//逆序(递归)
void LInkList::Reserve2()
{
    head->next = Reserve2(head->next);
}

//输出
void LInkList::show()
{
    std::cout<<"size ="<<size<<std::endl;
    Node * travelPoint = head->next;//存有效数据的第一个结点
    while(travelPoint != nullptr)//当前结点存在
    {
        std::cout<<travelPoint->value<<" ";//打印数据域
        travelPoint = travelPoint->next;//访问下一个结点
    }
    std::cout<<std::endl;
}

LInkList:: Node * LInkList::Reserve2(Node *node)
{
    //返回值是新链表的头
    //终止条件
    if(node->next == nullptr)//原来的尾巴是新的头
        return node;
    else
    {
        Node *newHeader = Reserve2(node->next);
        node->next->next = node;//真正的逆序
        node->next = nullptr;//新尾巴next指针指向空
        return newHeader;
    }
    
}

// 快慢指针法则
void LInkList::FastSort(Node *start, Node *end)
{
    if(start == end)
        return;
    Node *temp = start;//基准值指针
    Node *slow = start;//慢指针
    Node *fast = start->next;
    while(fast != end)
    {
        if(fast->value < temp->value)
        {
            slow = slow->next;
            std::swap(fast->value,slow->value);
        }
        fast = fast->next;
    }
    std::swap(temp->value,slow->value);

    FastSort(start,slow);
    FastSort(slow->next,end);
}

LInkList LInkList::Merge2(LInkList *list[], int start, int end)
{
    if (start == end)
        return *list[start];
    if (start < end)
    {
        //int mid = start + (end - start) / 2;
        int mid = (start + end) / 2;
        LInkList left = Merge2(list, start, mid);
        LInkList right = Merge2(list, mid + 1, end);
        return left.Merge(right);
    }
    return LInkList();
}